TNotes.leetcode

Appearance

0012. 整数转罗马数字【中等】

0012. 整数转罗马数字【中等】 ​

1. 📝 题目描述 ​

七个不同的符号代表罗马数字，其值如下：

符号值
I1
V5
X10
L50
C100
D500
M1000

罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

  • 如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
  • 如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
  • 只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5(V)，50 (L) 或 500 (D)。如果需要将符号附加 4 次，请使用减法形式。

给定一个整数，将其转换为罗马数字。

示例 1：

txt
输入：num = 3749
输出："MMMDCCXLIX"

解释：

  • 3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
  • 700 = DCC 由于 500 (D) + 100 (C) + 100 (C)
  • 40 = XL 由于 50 (L) 减 10 (X)
  • 9 = IX 由于 10 (X) 减 1 (I)

注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位

示例 2：

txt
输入：num = 58
输出："LVIII"

解释：

  • 50 = L
  • 8 = VIII

示例 3：

txt
输入：num = 1994
输出："MCMXCIV"

解释：

  • 1000 = M
  • 900 = CM
  • 90 = XC
  • 4 = IV

提示：

  • 1 <= num <= 3999

2. 🎯 s.1 - 贪心 + 映射表 ​

c
char* intToRoman(int num) {
    int vals[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    char* syms[] = {"M",  "CM", "D",  "CD", "C",  "XC", "L",
                    "XL", "X",  "IX", "V",  "IV", "I"};
    int n = 13;

    char* ans = (char*)malloc(20 * sizeof(char));
    ans[0] = '\0';
    for (int i = 0; i < n; i++) {
        while (num >= vals[i]) {
            strcat(ans, syms[i]);
            num -= vals[i];
        }
    }
    return ans;
}
js
/**
 * @param {number} num
 * @return {string}
 */
var intToRoman = function (num) {
  const vals = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
  const syms = [
    'M',
    'CM',
    'D',
    'CD',
    'C',
    'XC',
    'L',
    'XL',
    'X',
    'IX',
    'V',
    'IV',
    'I',
  ]

  let ans = ''
  for (let i = 0; i < vals.length; i++) {
    while (num >= vals[i]) {
      ans += syms[i]
      num -= vals[i]
    }
  }
  return ans
}
py
class Solution:
    def intToRoman(self, num: int) -> str:
        vals = [1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1]
        syms = ["M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"]

        ans = ""
        for v, s in zip(vals, syms):
            while num >= v:
                ans += s
                num -= v
        return ans
  • 时间复杂度：O(1)，映射表长度固定为 13，循环次数有上界
  • 空间复杂度：O(1)，只使用了常数大小的映射表和结果字符串

算法思路：

  • 预先按降序编写全部 13 个有效符号及对应整数值（含六个减法叠加形式）
  • 从大到小贪心地循环：只要 num >= vals[i]，就不断拼接 syms[i] 并减去对应值，直到当前符号不再适用

Discussions